package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.UUID;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/5/24 下午2:07
 */
public class 滑动窗口的最大值 {

    public static void main(String[] args) {

        UUID uuid = UUID.randomUUID();
        System.out.println(uuid);


        //System.out.println(Arrays.toString(maxSlidingWindow(new int[]{5,4,3,2,1},3)));

    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        // 结果数组
        // 结果个数：nums.length - (k - 1)
        List<Integer> res = new ArrayList<>(nums.length - (k - 1));
        // 临时数组
        List<Integer> temp = new ArrayList<>(k);
        for (int i = 0; i < nums.length; i++) {

            // num[i] > temp[len - 1]
            while (i > 0 && temp.size() > 0 && nums[i] >= temp.get(temp.size() - 1)){
                temp.remove(temp.size() - 1);
            }

            temp.add(nums[i]);

            if (i >= k && nums[i - k] == temp.get(0)){
                temp = temp.subList(1,temp.size());
            }

            if (i >= k - 1){
                res.add(temp.get(0));
            }
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}
